import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        zigzagHelper(root, 0, result);
        return result;
    }

    private void zigzagHelper(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) return;

        if (level == result.size()) {
            result.add(new ArrayList<>());
        }

        // 根据层级的奇偶性决定顺序
        if (level % 2 == 0) {
            result.get(level).addLast(node.val);       // 偶数层从左到右
        } else {
            result.get(level).addFirst(node.val);    // 奇数层从右到左，头部插入
        }

        zigzagHelper(node.left, level + 1, result);
        zigzagHelper(node.right, level + 1, result);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test Case 1: 空树
        System.out.println("Case 1: " + sol.zigzagLevelOrder(null));
        // 期望输出: []

        // Test Case 2: 单节点
        TreeNode root1 = new TreeNode(1);
        System.out.println("Case 2: " + sol.zigzagLevelOrder(root1));
        // 期望输出: [[1]]

        // Test Case 3: 完全二叉树
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(5);
        root2.right.left = new TreeNode(6);
        root2.right.right = new TreeNode(7);
        System.out.println("Case 3: " + sol.zigzagLevelOrder(root2));
        // 期望输出: [[1], [3, 2], [4, 5, 6, 7]]

        // Test Case 4: 非完全二叉树
        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(3);
        root3.left.left = new TreeNode(4);
        root3.right.right = new TreeNode(5);
        System.out.println("Case 4: " + sol.zigzagLevelOrder(root3));
        // 期望输出: [[1], [3, 2], [4, 5]]

        // Test Case 5: 只有左子树
        TreeNode root4 = new TreeNode(1);
        root4.left = new TreeNode(2);
        root4.left.left = new TreeNode(3);
        root4.left.left.left = new TreeNode(4);
        System.out.println("Case 5: " + sol.zigzagLevelOrder(root4));
        // 期望输出: [[1], [2], [3], [4]]
    }
}
